package algorithm
{
	import datastructure.EdgeAbstract;
	import datastructure.Graph;

	/**
	 * 构造最小生成树的 Kruskal算法
	 * @author juxuan
	 * 
	 */	
	public class Kruskal
	{
		private var mstKru:Array;	//组成图的最小生成树的边的集合
		private var versMstKru:Array;	//最小生成树的顶点集合
		private var ecounter:int;	//边的集合的规模
		private var k:int;	//已处理的边的数量
		
		private var graph:Graph;
		public var oriEdges:Array;
		
		private var p:Array;	//p[x]表示x节点父节点
		private var rank:Array;	//树节点的秩
		
		public function Kruskal(g:Graph,originVerArray:Array = null)
		{
			this.ecounter = 0;
			this.k = 0;
			this.mstKru = new Array();
			
			this.oriEdges = new Array();
			this.graph = g;
			initOriEdges();
			
			this.p = new Array(this.graph.verNum());
			this.rank = new Array();
			//runKruskal();
		}
		
		/**
		 * 运行 Kruskal算法
		 * 
		 */		
		public function runKruskal():void
		{
			initUnionFind();
			while(this.ecounter < (this.graph.verNum() - 1))
			{
				var edge:EdgeAbstract = this.oriEdges.shift();
				k++;
				if(!isCircle(edge))
				{
					this.mstKru.push(edge);
					this.ecounter ++;
					this.union(edge.start,edge.end);
				}
			}
		}
		
		/**
		 * 判断是否存在回路
		 * @param mstKru
		 * @param edge
		 * @return 
		 * 
		 */		
		private function isCircle(edge:EdgeAbstract):Boolean
		{
			var start:int = edge.start;
			var end:int = edge.end;
			if(isSameParent(start,end))
				return true;
			
			return false;
		}
		
		public function getMstKru():Array
		{
			return this.mstKru;
		}
		
		
		
		/**
		 * 初始化图的边集合 
		 * 
		 */		
		private function initOriEdges():void
		{
			var versNum:int = this.graph.verNum();
			trace("length:" + versNum);
			for(var i:int = 0; i < versNum; i++)
			{
				for(var j:int = 0; j < versNum; j++)
				{
					if(this.graph.weight(i,j) != 0)
					{
						if(!isExits(this.oriEdges,i,j))
						{
							var edge:EdgeAbstract = new EdgeAbstract(i,j,this.graph.weight(i,j));
							this.oriEdges.push(edge);
						}
						
					}
				}
			}
			this.oriEdges.sortOn("weight",Array.NUMERIC);
		}
		
		/**
		 * 防止无向图的边重复添加 
		 * @param oriEdges
		 * @param s
		 * @param e
		 * @return 
		 * 
		 */		
		private function isExits(oriEdges:Array,s:int,e:int):Boolean
		{
			for(var i:int = 0;i < oriEdges.length;i++)
			{
				if((oriEdges[i].start == e) && (oriEdges[i].end == s))
				{
					//trace("dadsada:" + s + " " + e);
					return true;
				}
			}
			
			return false;
		}
		
		
		/**
		 * 为并查算法做准备 
		 * 
		 */		
		private function initUnionFind():void
		{
			for(var i:int = 0; i < this.graph.verNum();i++)
			{
				this.makeset(i);
			}
		}
		
		
		/*~~~~~~~~~~~~~~并查算法部分~~~~~~~~~~~~~~~*/
		
		/**
		 * 创建一棵单节点的树 
		 * @param i
		 * 
		 */		
		private function makeset(i:int):void
		{
			this.p[i] = i;
			this.rank[i] = 0
		}
		
		/**
		 * 从包含x的节点开始找到树的根，返回跟 
		 * @param x
		 * 
		 */		
		private function find(x:int):int
		{
			if(this.p[x] == x)
				return x;
			else
				return find(this.p[x]);
		}
		
		/**
		 * 判断两个节点是否在同个子集 
		 * @param x
		 * @param y
		 * @return Boolean
		 * 
		 */		
		private function isSameParent(x:int,y:int):Boolean
		{
			if(find(x) == find(y))
				return true;
			else
				return false;
		}
		
		/**
		 * 合并两个子集 
		 * @param x
		 * @param y
		 * 
		 */		
		private function union(x:int,y:int):void
		{
			var xParent:int = find(x);
			var yParent:int = find(y);
			
			if(xParent != yParent)
			{
				if(this.rank[xParent] > this.rank[yParent])
				{
					this.p[yParent] = xParent;
				}
				else
				{
					this.p[xParent] = yParent;
					if(this.rank[xParent] == this.rank[yParent])
					{
						this.rank[yParent] ++;
					}
					
				}
				
				
			}
			
			
		}
		
		
			
		
		
		
		
		
		
		
	}
}